package day1.TraversalBinaryTree;

import java.util.HashMap;

/**
 * @author pacai
 * @version 1.0
 * 根据先序遍历和中序遍历构建出二叉树
 */
public class ConstructBinaryTree {
    public static class TreeNode<T> {
        T data;
        TreeNode<T> left;
        TreeNode<T> right;

        public TreeNode(T data) {
            this.data = data;
        }
    }

    public static TreeNode<Integer> buildTree(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length != in.length) {
            return null;
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            hashMap.put(in[i], i);
        }
        return f(pre, 0, pre.length - 1, in, 0, in.length - 1, hashMap);
    }

    public static TreeNode<Integer> f(int[] pre, int L1, int R1, int[] in, int L2, int R2,
                                      HashMap<Integer, Integer> hashMap) {
        if (L1 > R1) return null;
        TreeNode<Integer> head = new TreeNode<>(pre[L1]);
        if (L1 == R1) return head;
        int find = hashMap.get(pre[L1]);//从表中直接得到对应位置，无需遍历
//        while (in[find] != pre[L1]) {
//            find++;
//        }
        head.left = f(pre, L1 + 1, L1 + find - L2, in, L2, find - 1, hashMap);
        head.right = f(pre, L1 + find - L2 + 1, R1, in, find + 1, R2, hashMap);
        return head;
    }

}
